package com.zy.sort;

import java.util.List;

/**
 * @description: 快速排序
 * @author: zhaoyi
 * @create: 2019-12-04 21:32
 **/

public class QuickSort<T extends Comparable<? super T>> {


    /**
     * 第一步先写放正确划分点的方法
     *
     * @param list
     */
    public void sort(List<T> list) {
        if (list == null || list.size() <= 1) {
            return;
        }

        correctPosition(list, 0, list.size() - 1);
    }

    /**
     * 取right位置的点放在正确位置上使得左边的都小于等于他，右边都大于他
     * @param list
     * @param left
     * @param right
     */
    public void correctPosition(List<T> list, int left, int right) {

        if (left >= right) {
            return;
        }

        int index = right;
        int li = left;
        int ri = right;
        right--;
        boolean lf = false;
        boolean rf = false;
        int cp = 0;
        while (right >= left) {
            cp = right;

            T r = list.get(right);
            T l = list.get(left);

            if (right - left == 1) {
                //优先看左边比最后一个大
                if (l.compareTo(list.get(index)) > 0) {
                    list.set(left, list.get(index));
                    list.set(index, l);
                    cp = left;
                } else if (r.compareTo(list.get(index)) > 0) {
                    list.set(right, list.get(index));
                    list.set(index, r);
                    cp = right;
                }
                break;
            }

            if (right == left) {
                if (list.get(index).compareTo(r) < 0) {
                    list.set(right, list.get(index));
                    list.set(index, r);
                }
                break;
            }

            if (!rf && r.compareTo(list.get(index)) >= 0) {
                right--;
            } else {
                rf = true;
            }
            if (!lf && l.compareTo(list.get(index)) <= 0) {
                left++;
            } else {
                lf = true;
            }
            if (lf && rf) {
                list.set(right, l);
                list.set(left, r);
                lf = false;
                rf = false;
                right--;
                left++;
            }

        }
        correctPosition(list, li, cp - 1);
        correctPosition(list, cp + 1, ri);


    }

}
